欧拉回路 [构造题] 欧拉回路 [构造题] Wannafly Day3 D 虽说是构造题，实际这题并没有要求构造，只需输出最值即可。 题目来源：comet OJ 分析 对于这题，我们可以向欧拉回路的性质上去靠。首先我们都知道，欧拉回路的所有的点的度数都为偶数。那么，我们可以首先假设所有的边都被走过了一遍，此时我们可以得到一个此时的所有的点各自的度数的值。 那么，我们的目标便是令这些值都为偶数。方法则为将临近的两个奇数度数的点的连边走的次数+1，此时这两个点的度数都会便为偶数。若它们不相邻，则通过连边可以令度数为奇数的点的位置发生移动，最后移到相邻为止即可。 那么，消去某两个奇数度数点的代价其实就相当于它们之间的曼哈顿距离。而对于题目给出的这个矩形的图，所有奇数点都会出现在非四个顶点位置的四个边上。那么，我们便先将相邻的消掉，然后在对剩下的几个特殊判断处理即可。 代码 1234567891011121314151617181920212223242526272829#include <iostream>#include <algorithm>using namespace std;int main(){ int n, m; cin >> n >> m; int ans = 0; ans += (n-1) * m + (m-1) * n; if (n%2==0 && m%2==0) { ans += n - 2 + m - 2; }else if (n%2==1 && m%2==1) { ans += n - 3 + m - 3 + 4; }else if (n%2==0 && m%2==1) { ans += n - 2 + m - 3 + min(3, n - 1); }else if (n%2==1 && m%2==0) { ans += n - 3 + m - 2 + min(3, m - 1); } cout << ans << endl;}